import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * Klasa zawiera metody sluzace do generowania danych uzywanych w programie.
 * Zawiera metode generujaca instancje podzialu zbioru (losowy zbior elementow o
 * okreslonej liczbie elementow) oraz przestrzen stanow (zbior wszytskich
 * mozliwych, unikatowych rowiazan podzialow zbioru).
 * 
 * @author Ewa Byra (nr indeksu s6405)
 */
public class Generator {

	private static Random generator = new Random();

	/**
	 * Metoda sluzy do generowania danych wejsciowych - instancji problemu
	 * podzialu zbioru. Wywolywana przez akcje przycisku 'Generuj dane we' w
	 * klasie {@link GUI} lub poprzez samo uruchomienie programu (w
	 * konstruktorze klasy {@link GUI}).
	 * 
	 * @param size
	 *            Ilosc elementow w zbiorze.
	 * @return Liste elementow zbioru.
	 */
	public static List<Integer> generateData(int size) {
		List<Integer> data = new ArrayList<>();
		int randomInt;

		for (int i = 1; i <= size; i++) {
			randomInt = generator.nextInt(100);
			data.add(randomInt);
		}

		Collections.sort(data);
		return data;
	}

	/**
	 * Metoda sluzy do wygenerowania wszytskich uniaktowych podzialow zbioru.
	 * Wraz z okresleniem ich sasiedztwa. Wywolywana jest w kostruktorze klasy
	 * {@link MultiHillClimbingAlgorithm}.
	 * 
	 * @param data
	 *            Zbior elementow.
	 * @return Lista mozliwych rozwiazan problemu wraz z okreslonym ich
	 *         sasiedztwem.
	 */
	public static List<Partition> generateDataToHillClimbingAlgorithm(
			List<Integer> data) {
		List<Partition> partitions = new ArrayList<>();

		/* Generowanie przestrzeni stanow */
		partitions = generateSubLists(data);

		/* Szukanie rozwiazan sasiednich */
		for (int i = 0; i < partitions.size(); i++) {
			for (int j = i + 1; j < partitions.size(); j++) {
				if (isNeighbor(partitions.get(i), partitions.get(j))) {
					partitions.get(i).addNeighor(partitions.get(j));
					partitions.get(j).addNeighor(partitions.get(i));
				}
			}
		}

		return partitions;
	}

	/**
	 * Metoda uzywana do wydenerowania unikatowych rozwiazan problemu.
	 * 
	 * @param data
	 *            Instancja problemu.
	 * @return Liste wszystkich mozliwych rozwiazan problemu.
	 */
	private static List<Partition> generateSubLists(List<Integer> data) {

		/* Lista rozwiazan */
		List<Partition> partitions = new ArrayList<>();

		/* Listy pomocnicze */
		List<Partition> tempPartitions = new ArrayList<>();
		List<Partition> tempPartitions2 = new ArrayList<>();

		/* Podzbior elementow */
		List<Integer> firstSubSet = new ArrayList<>();

		/* Wygenerowane rozwiazanie */
		Partition generatedPartition;

		/*
		 * Maksymalna liczba elementow w pierwszym podzbiorze
		 */
		int n = (data.size() / 2) - 1;

		/*
		 * Generowanie podzialow z jednym elementem w pierwszym podzbiorze.
		 */
		for (int i = 0; i < data.size(); i++) {

			firstSubSet.add(data.get(i));

			/*
			 * Metoda zwraca podzial zbioru
			 */
			generatedPartition = getPartition(data, firstSubSet);

			/*
			 * Sprawdzanie, czy dany podzial nie znajduzje sie juz w zbiorze
			 * rozwiazan
			 */
			if (!hasPartition(partitions, generatedPartition)) {
				partitions.add(generatedPartition);
			}

			firstSubSet.clear();
		}

		tempPartitions.addAll(partitions); /* Kopia wygenerowanych podzialow */

		/*
		 * Generowanie reszty podzialow w oparciu o wygenerowane wczesniej
		 * podzialy.
		 */
		for (int i = 0; i < n; i++) {

			for (Partition p : tempPartitions) {

				firstSubSet.addAll(p.getFirstSubSet());

				for (int j = 0; j < p.getSecondSubSet().size(); j++) {

					/*
					 * Sprawdzanie pomaga uniknac wygenerowania istiejacych juz
					 * podzialow
					 */
					if (p.getSecondSubSet().get(j) >= p.getFirstSubSet().get(
							p.getFirstSubSet().size() - 1)) {

						firstSubSet.add(p.getSecondSubSet().get(j));

						/*
						 * Metoda zwraca podzial zbioru.
						 */
						generatedPartition = getPartition(data, firstSubSet);

						/*
						 * Sprawdzanie czy istnieje dany podzial w zbiorze
						 * rozwiazan/
						 */
						if (!hasPartition(partitions, generatedPartition)) {
							partitions.add(generatedPartition);
							tempPartitions2.add(generatedPartition);
						}
						firstSubSet.remove(p.getSecondSubSet().get(j));
					}
				}
				firstSubSet.clear();
			}
			tempPartitions.clear();

			/* Kopiujemy zawartosc z drugiej listy pomocniczej do pierwszej */
			tempPartitions.addAll(tempPartitions2);

			tempPartitions2.clear();
		}

		return partitions;
	}

	/**
	 * Metoda koduje binarnie rozwiazanie. Uzywana do znajdowania rozwiazan
	 * sasiednich.<br>
	 * Kodowanie binarne wyglada nastepujaco:<br>
	 * 1. Posortowac liste danych wejsciowych (wartosci elementow zbiorow) od
	 * najmniejszego do najwiekszego,<br>
	 * 2. Sprawdzane jest kolejno polozenie kazdego z elementow zbioru w
	 * podzbiorach. Gdy dany element znajduje sie w pierwszym podzbiorze
	 * dodawane jest do kodu wartosc 0, natomiast, gdy w drugim podzbiorze
	 * wartosc 1.<br>
	 * 
	 * @param partition
	 *            Rozwiazanie do zakodowania.
	 * @return Kod binarny rozwiazania.
	 */
	private static String getBinaryCode(Partition partition) {

		/* Zbor wszytskoch elementow zbioru */
		List<Integer> set = new ArrayList<>();
		set.addAll(partition.getFirstSubSet());
		set.addAll(partition.getSecondSubSet());

		/* Sortowanie zbioru */
		Collections.sort(set);

		String code = ""; /* Kod binarny */
		List<Integer> firstSubSet = new ArrayList<>();
		List<Integer> secondSubSet = new ArrayList<>();

		firstSubSet.addAll(partition.getFirstSubSet());
		secondSubSet.addAll(partition.getSecondSubSet());

		for (int i = 0; i < set.size(); i++) {
			if (firstSubSet.contains(set.get(i))) {
				code += "0";
				firstSubSet.remove(0);
			} else {
				code += "1";
				secondSubSet.remove(0);
			}
		}

		return code;
	}

	/**
	 * Metoda uzywana do utworzenia instancji rozwiazania problemu. Na podstawie
	 * pierwszego podzbioru oraz calego zbioru tworzy liste elementow drugiego
	 * pozdbioru, a nastepnie tworzy z tego instancje podzialu.
	 * 
	 * @param data
	 *            Zbior wszytskich elementow zbioru.
	 * @param el
	 *            Zbior elementow pierwszego podzbioru.
	 * @return Instancje rozwiazania problemu.
	 */
	private static Partition getPartition(List<Integer> data, List<Integer> el) {
		List<Integer> secondSubSet = new ArrayList<>();
		List<Integer> firstSubSet = new ArrayList<>();
		List<Integer> tempSubSet = new ArrayList<>();
		firstSubSet.addAll(el);
		tempSubSet.addAll(el);

		for (int i = 0; i < data.size(); i++) {
			if (tempSubSet.contains(data.get(i))) {
				for (int j = 0; j < tempSubSet.size(); j++) {
					if (tempSubSet.get(j) == data.get(i)) {
						tempSubSet.remove(j);
						break;
					}
				}
			} else {
				secondSubSet.add(data.get(i));
			}
		}

		return new Partition(firstSubSet, secondSubSet);
	}

	/**
	 * Metoda uzywana do sprawdzania czy na liscie rozwiazan znajduje sie podany
	 * element. Sprawdzenie pomaga w uniknieciu powtorzen.
	 * 
	 * @param partitions
	 *            Lista juz wygenerowanych rozwiazan problemu.
	 * @param partition
	 *            Rozwiazanie do sprawdzenia.
	 * @return Wartosc 'true' jezeli podane rozwiazanie znajduje sie na liscie.
	 */
	private static boolean hasPartition(List<Partition> partitions,
			Partition partition) {
		boolean result = false;

		if (partitions.size() != 0) {
			for (int i = partitions.size() - 1; i != 0; i--) {
				if (partitions.get(i).equals(partition)) {
					result = true;
					break;
				}
			}
		}
		
		return result;
	}

	/**
	 * Metoda sluzy do sprawdzania czy podane rozwiazania sa sasiednie.<br>
	 * Rozwiazania sasiednie roznia sie polozeniem co najwyzej jednego elementu
	 * w podzbiorach.<br>
	 * Na potrzeby ulatwienia szukania takich rozwiazan, sa one kodowane
	 * binarnie.<br>
	 * 
	 * @param partition
	 *            Rozwiazanie problemu do sprawdzenia.
	 * @param partition2
	 *            Drugie rozwiazanie problemu do sprawdzenia.
	 * @return Wartosc 'true' jezeli podane rozwiazania sa sasiednie.
	 */
	private static boolean isNeighbor(Partition partition, Partition partition2) {
		boolean result = false;

		/* Kodowanie rozwiazan w celu ulatwienia szukania roznic */
		String code1 = getBinaryCode(partition);
		String code2 = getBinaryCode(partition2);

		/* Sprawdzanie czy rozwiazania sa sasiednie */
		int count = 0; /* licznik roznic */
		for (int i = 0; i < code1.length(); i++) {
			if (code1.charAt(i) != code2.charAt(i))
				count++;
		}

		/*
		 * Jezeli rozwiazania maja jedna roznice badz pokryte sa tylko z jednym
		 * elementem (odwrotnosc ulozenia w podzbiorach) - sa rozwiazaniami
		 * sasiednimi
		 */
		if (count == 1 || count == code1.length() - 1)
			result = true;

		return result;
	}
}
